package com.lry.basic.algorithm.stack;

import java.util.Stack;

/**
 * @author:刘仁有
 * @desc:
 * @email:953506233@qq.com
 * @data:2019/12/5
 */
public class MinRemoveToMakeValid {
    /**
     * 给你一个由 '('、')' 和小写字母组成的字符串 s。
     * 你需要从字符串中删除最少数目的 '(' 或者 ')' （可以删除任意位置的括号)，使得剩下的「括号字符串」有效。
     * 请返回任意一个合法字符串。
     * 示例 1：
     * 输入：s = "lee(t(c)o)de)"
     * 输出："lee(t(c)o)de"
     * 解释："lee(t(co)de)" , "lee(t(c)ode)" 也是一个可行答案。
     *
     * 示例 2：
     * 输入：s = "a)b(c)d"
     * 输出："ab(c)d"
     *
     * 示例 3：
     * 输入：s = "))(("
     * 输出：""
     * 解释：空字符串也是有效的
     *
     * 示例 4：
     * 输入：s = "(a(b(c)d)"
     * 输出："a(b(c)d)"

     * @param args
     */
    public static void main(String[] args) {
        System.out.println(minRemoveToMakeValid("))(("));
    }
    public static String minRemoveToMakeValid(String s) {
        if(null==s||s.length()==0)
            return "";
        char[]chars = s.toCharArray();
        Stack<Integer>stack = new Stack<>();
        for (int i=0;i<chars.length;i++) {
            char c = chars[i];
            if(c=='('){
                stack.push(i);
            }else if(c==')'){
                if(!stack.isEmpty()){
                    if(chars[stack.peek()]=='('){
                        stack.pop();
                    }else{
                        stack.push(i);
                    }
                }else{
                    stack.push(i);
                }
            }
        }
        for (int i:stack) {
            chars[i]=' ';
        }
        return String.valueOf(chars).replaceAll(" ","");
    }
}
